package org.example.ch04;

/**
 * https://leetcode-cn.com/problems/climbing-stairs/
 * 爬楼梯问题
 * 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
 *
 * 每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
 *
 * 注意：给定 n 是一个正整数。
 */
public class ClimpStairs {

    public static void main(String[] args) {
//        int result = solution1(0,13);
//        int result = solution2(4);
        int result = solution3(4);
        System.out.println(result);
    }

    /**
     * 暴力破解
     * @param i
     * @param n
     * @return
     */
    public static int solution1(int i,int n){
        // 先写递归的终结条件
        if(i>n){
            return 0;
        }
        if(i==n){
            return 1;
        }
        return solution1(i+1,n)+solution1(i+2,n);
    }


    public static int solution2(int n){
        if(n==1){
            return 1;
        }
        if(n==2){
            return 2;
        }
        return solution2(n-1) + solution2(n-2);
    }

    public static int solution3(int n){
        int p=0,q=0,r=1;
        for (int i = 0; i < n ; i++) {
            p=q;
            q=r;
            r=p+q;
        }
        return r;
    }
}
